/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/add-binary
   @Language: C++
   @Datetime: 16-02-09 04:40
   */

class Solution {
public:
	/**
	 * @param a: a number
	 * @param b: a number
	 * @return: the result
	 */
	string addBinary(string &a, string &b) {
		// write your code here
		int n=a.length(), m=b.length();
		string res(max(n,m)+1,'0');
		for(int i=n, j=m, k=max(n,m), carry=0; i || j || carry;){
			if (i) carry += a[--i]-'0';
			if (j) carry += b[--j]-'0';
			res[k--]=carry%2+'0';
			carry /=2;
		}
		if (res[0]=='0') res.erase(0,1);
		return res;
	}
};
